package com.java.container;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * @program: java_basic_knowledge
 * @description:
 * @author: CaoYong
 * @create: 2021-04-14 10:32
 * LinkedList特点：
 * 1. 按需分配空间，不需要预先分配很多空间
 * 2. 不可以随机访问，按索引访问必须从头或尾开始找，效率O(n/2)
 * 3. 不管是否已排序，按内容查找只能从头访问， 效率O(n)
 * 4. 在两端添加元素效率高， 为O(1)
 * 5. 在中间删除，插入元素，要先定位效率比较低，为O(n)
 **/
public class LinkedListKnowledge {

    /**
     * LinkedList实现了DeQueue和Queue接口，其中DeQueue中定义的栈的相关方法，Queue定义了队列的相关方法，因此LinkedList可以做为栈或者队列使用
     * LinkedList的内部实现是双向链表
     * @param <E>
     */
    public static class HowToDefineLinkedList<E> implements DefineDeQueue{

        /**
         * LinkedList类包含三个实例变量
         */
        int size; // 链表长度
        Node<E> first; // 头节点
        Node<E> last; // 尾节点

        int modCount; //操作数

        public HowToDefineLinkedList() {
        }

        public boolean add(E e) {
            linkLast(e);
            return true;
        }

        public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }

        public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }

        private E unlink(Node<E> x) {
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;

            if(prev == null) {
                first = next;
            } else {
                prev.next = next;
            }
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
            x.item = null;
            size --;
            modCount ++;
            return element;
        }

        public int intdexOf(Object o) {
            int index = 0;
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if(x.item == null) {
                        return index;
                    }
                    index ++;
                }
            } else {
                for(Node<E> x = first; x != null; x = x.next) {
                    if(o.equals(x.item)) {
                        return index;
                    }
                    index ++;
                }
            }
            return -1;
        }

        /**
         * 链表中的查找，首先判断index是大于size / 2 还是小于 size / 2，如果是小于则从头还是查找，否则从尾部开始查找。相对于每次都从头遍历而言有一些优化
         * @param index
         * @return
         */
        private Node<E> node(int index) {
            if(index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++) {
                    x = x.next;
                }
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index ; i--) {
                    x = x.prev;
                }
                return x;
            }
        }

        private void checkElementIndex(int index) {
            if(index < 0 || index >=size) {
                throw new IndexOutOfBoundsException();
            }
        }


        // 尾插法
        private void linkLast(E e) {
            final Node<E> l = last; //l和last都指向尾节点
            final Node<E> newNode = new Node(l, e, null); //创建一个新节点，其prev指向last节点
            last = newNode; // last节点的指向新节点
            if (l == null) { // 如果原来的链表为空则让头结点指向新节点，否则让前一个节点的next新节点
                first = newNode;
            }
            else {
                l.next = newNode;
            }
            size ++;
            modCount ++;
        }

        /**
         * LinkedList内部定义的内部节点类
         * @param <E>
         */
        public static class Node<E> {
            E item;
            Node<E> next;
            Node<E> prev;

            public Node(Node<E> prev, E item, Node<E> next) {
                this.prev = prev;
                this.item = item;
                this.next = next;
            }
        }




    }

    // 双端队列DeQueue的定义
    public interface DefineDeQueue<E> extends DefineQueue<E>{
//        void push(E e); //入栈，头部添加元素，栈满抛出illegalStateException
//        E pop(); // 出栈, 返回头部元素并从栈中删除，栈空抛出NoSuchElementException
//        @Override
//        E peek(); //查看头部元素，,不删除元素，栈空返回null
//        Iterator<E> descendingIterator(); // 可以利用迭代器从后往前遍历
    }

    // 队列接口Queue的定义
    public interface DefineQueue<E> {
//        boolean add(E e); // 在尾部添加元素, 队列满时抛出illegalStateException
//        boolean offer(E e); // 在尾部添加元素, 队列满时返回false
//        E remove(); // 返回头部元素，但不改变队列，在队列为空的时候抛出NoSuchElementException
//        E poll(); // 返回头部元素，但不改变队列, 在队列为空时返回null
//        E element(); // 返回头部元素，并且从队列中删除, 在队列为空的时候抛出NoSuchElementException
//        E peek(); // 返回头部元素，并且从队列中删除, 在队列为空时返回null
    }
}
